#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define mp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
vector<int> prime;

int main() {
  freopen("evod.in", "r", stdin);
  freopen("evod.out", "w", stdout);
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  for (int i = 2; i <= 10000; i++) {
    bool flag = 1;
    for (int j = 2; j <= sqrt(i); j++) {
      if (i % j == 0) {
        flag = 0;
      }
    }
    if (flag) {
      prime.push_back(i);
    }
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int tmp;
    cin >> tmp;
    vector<int>::iterator it = find(prime.begin(), prime.end(), tmp);
    if (it != prime.end()) {
      it++;
      cout << *it << " ";
    } else if (tmp % 2 == 1) {
      cout << tmp + 1 << " ";
    } else if (tmp % 2 == 0) {
      cout << tmp - 1 << " ";
    }
  }
  //   fclose(stdin);
  //   fclose(stdout);
  return 0;
}
